//
//  LevelOrder.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/7.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  102. 二叉树的层序遍历

import UIKit

/*
 102. 二叉树的层序遍历
 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

  

 示例：
 二叉树：[3,9,20,null,null,15,7],

     3
    / \
   9  20
     /  \
    15   7
 返回其层次遍历结果：

 [
   [3],
   [9,20],
   [15,7]
 ]
 */

class LevelOrder: NSObject {
    
    
    func levelOrder(_ root: TreeNode?) -> [[Int]] {

        var resultArr:[[Int]] = []
        var queue:[TreeNode]! = []
        
        guard root != nil else{
            return resultArr
        }
        queue.append(root!)
        
        while queue.isEmpty == false {
            var arr = [Int]()
            for _ in queue{
                let first = queue.first
                queue.removeFirst()
                arr.append(first!.val)
                if first?.left != nil {
                    queue.append(first!.left!)
                }
                if first?.right != nil {
                    queue.append(first!.right!)
                }
            }
            resultArr.append(arr)
        }
        
        return resultArr
    }
    
    
    
    /*
     637. 二叉树的层平均值
     */
    func averageOfLevels(_ root: TreeNode?) -> [Double] {
        var resultArr:[Double] = []
        var queue:[TreeNode]! = []
        
        guard root != nil else{
            return resultArr
        }
        queue.append(root!)
        
        while queue.isEmpty == false {
            var arr = [Int]()
            for _ in queue{
                let first = queue.first
                queue.removeFirst()
                arr.append(first!.val)
                if first?.left != nil {
                    queue.append(first!.left!)
                }
                if first?.right != nil {
                    queue.append(first!.right!)
                }
            }
            resultArr.append(self.getAveFromArray(arr))
        }
        
        return resultArr
    }
    
    func getAveFromArray(_ arr:[Int])->Double{
        var sum = 0
        for num in arr{
            sum = sum + num
        }
        return Double(sum)/Double(arr.count)
    }
    
}
